package org.laizili.solution.codinginterviews;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * <a href="https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/">剑指offer 50. 第一个只出现一次的字符</a>
 * <p>
 * tags: 哈希表；队列
 * <p>
 * notes: 2022阅文集团暑期实习面试题
 * <p>
 * 扩展：计算出现两次的字符中倒数第2次出现的字符
 * 例如 aabbcc, a,b,c均出现了2次，b是倒数第2个出现两次的字符
 */
public class ProblemOffer50 {
    private static class Solution {
        // hashmap 解法
        // 遍历两次字符串
        public char firstUniqChar(String s) {
            // char-count 映射
            Map<Character, Integer> ch2Cnt = new HashMap<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                int cnt = ch2Cnt.getOrDefault(ch, 0) + 1;
                ch2Cnt.put(ch, cnt);
            }
            // 再次遍历字符串，查找第一次出现的字符
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch2Cnt.get(ch) == 1) {
                    return ch;
                }
            }
            return ' ';
        }
    }

    private static class Solution2 {
        // 队列 解法
        //
        public char firstUniqChar(String s) {
            Map<Character, Integer> ch2Cnt = new HashMap<>();
            Queue<Character> queue = new LinkedList<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (!ch2Cnt.containsKey(ch)) {
                    ch2Cnt.put(ch, i);
                    queue.offer(ch);
                } else {
                    ch2Cnt.put(ch, -1);
                    //
                    // 队列维护:
                    //    队首始终维护首次出现一次的字符
                    while (!queue.isEmpty() && ch2Cnt.get(queue.peek()) == -1) {
                        queue.poll();
                    }
                }
            }
            if (queue.isEmpty())
                return ' ';
            return queue.peek();
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution2().firstUniqChar("google"));
    }
}
